This Page Is Inserted by IFW Operations
and is not a part of the Official Record
BEST AVAILABLE IMAGES
Defective images within this document are accurate representations of the
original documents submitted by the applicant.
Defects in the images may include (but are not limited to):
• BLACK BORDERS
• TEXT CUT OFF AT TOP, BOTTOM OR SIDES
• FADED TEXT
• ILLEGIBLE TEXT
• SKEWED/SLANTED IMAGES
• COLORED PHOTOS
• BLACK OR VERY BLACK AND WHITE DARK PHOTOS
• GRAY SCALE DOCUMENTS
IMAGES ARE BEST AVAILABLE COPY.
As rescanning documents will not correct images,
please do not report the images to the
Image Problems Mailbox.
WORLD INTELLECTUAL PROPERTY ORGANIZATION
International Bureau
PCT
INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
(51) International Patent Classification 6
H04L 9/00
Al
(11) International Publication Number: WO 97/26733
(43) International Publication Date: 24 July 1997 (24.07.97)
(21) International Application Number: PCT/US97/00652
(22) Internationa] Filing Date: 17 January 1997 (17.01.97)
(30) Priority Data:
08/587,944
17 January 1996 (17.01.96)
US
(71) Applicant: THE DICE COMPANY [US/US]; Townhouse 4,
20191 E. Country Club Drive, Avenrura, FL 33180 (US).
(72) Inventors: COOPERMAN, Marc; 2929 Ramona, Palo Alto,
CA 94306 (US). MOSKOWITZ, Scott, A.; Townhouse 4,
20191 E. Country Club Drive, Avenrura. FL 33180 (US).
(74) Agents: ALTM1LLER, John, C. el al.; Kenyon & Kenyon, 1025
Connecticut Avenue, N.W., Washington, DC 20036 (US).
(81) Designated States: AL, AU, BA, BB, BG. BR, CA, CN, CU,
CZ, EE, GE, HU, IL, IS, JP. KP, KR, LC, LK, LR, LT, LV,
MG, MK, MN, MX, NO, NZ, PL, RO, SG, SI, SK, TR, TT,
UA, UZ, VN, ARIPO patent (KE, LS, MW, SD, SZ, UG),
Eurasian patent (AM, AZ, BY, KG. KZ, MD f RU, TJ, TM).
European patent (AT, BE, CH, DE, DK, ES, FI, FR t GB,
GR, IE, IT, LU, MC, NL, PT, SE), OAPI patent (BF, BJ,
CF, CG, CI. CM, GA, GN, ML, MR, NE, SN, TD t TG).
Published
With international search report
Before the expiration of the time limit for amending the
claims and to be republished in the event of the receipt of
amendments.
(54) Title: METHOD FOR AN ENCRYPTED DIGITAL WATERMARK
(57) Abstract
A method for the human-assisted generation and application of pseudo-random keys for the purpose of encoding and decoding digital
watermarks to and from a digitized data stream. A pseudo-random key and key application "envelope" are generated and stored using
guideline parameters input by a human engineer interacting with a graphical representation of the digitized data stream. Key "envelope"
information is permanently associated with the pseudo-random binary string comprising the key. Key and "envelope" information are then
applied in a digital watermark system to the encoding and decoding of digital watermarks.
FOR THE PURPOSES OF INFORMATION ONLY
Codes used to identify States party to the PCT on the front pages of pamphlets publishing international
applications under the PCT.
AM
Armenia
GB
United Kingdom
MW
Malawi
AT
Austria
GE
Georgia
MX
Mexico
AU
Australia
GN
Guinea
NE
Niger
BB
Barbados
GR
Greece
NL
Netherlands
BE
Belgium
HU
Hungary
NO
Norway
BF
Burkina Faso
IE
Ireland
NZ
New Zealand
BG
Bulgaria
IT
Italy
PL
Poland
BJ
Benin
JP
Japan
PT
Portugal
BR
Brazil
KE
Kenya
RO
Romania
BY
Belarus
KG
Kyrgystan
Ril
Russian Federation
CA
Canada
KP
Democratic People's Republic
SD
Sudan
CF
Central African Republic
of Korea
SE
Sweden
CC
Congo
KR
Republic of Korea
sc
Singapore
CH
Switzerland
KZ
Kazakhstan
SI
Slovenia
CI
Cote d'lvoire
U
Liechtenstein
SK
Slovakia
CM
Cameroon
LK
Sri Lanka
SN
Senegal
CN
China
LR
Liberia
sz
Swaziland
CS
Czechoslovakia
LT
Lithuania
TD
Chad
cz
Czech Republic
LU
Luxembourg
TC
Togo
DE
Germany
LV
Latvia
TJ
Tajikistan
DK
Denmark
MC
Monaco
TT
Trinidad and Tobago
EE
Estonia
MD
Republic of Moldova
UA
Ukraine
ES
Spain
MG
Madagascar
uc
Uganda
Fl
Finland
ML
Mali
us
United States of America
FR
France
MN
Mongolia
uz
Uzbekistan
GA
Gabon
MR
Mauritania
VN
Viet Nam
WO 97/26733
PCT7US97/00652
METHOD FOR AN ENCRYPTED DIGITAL WATERMARK
FIELD OF INVENTION
5 With the advent of computer networks and digital
multimedia, protection of intellectual property has
become a prime concern for creators and publishers of
digitized copies of copyrightable works, such as musical
recordings, movies, and video games. One method of
0 protecting copyrights in the digital domain is to use
"digital watermarks" . Digital watermarks can be used to
mark each individual copy of a digitized work with
information identifying the title, copyright holder, and
even the licensed owner of a particular copy. The
5 watermarks can also serve to allow for secured metering
and support of other distribution systems of given media
content and relevant information associated with them,
including addresses, protocols, billing, pricing or
distribution path parameters, among the many things that
0 could constitute a "watermark." For further discussion
of systems that are oriented around content -based
addresses and directories, see U.S. Patent No. 5,428,606
Moskowitz. When marked with licensing and ownership
information, responsibility is created for individual
> copies where before there was none. More information on
digital watermarks is set forth in "Steganographic
Method and Device" - The DICE Company, U.S. application
Serial No. 08/4 89,172, the disclosure of which is hereby
incorporated by reference. Also, "Technology: Digital
WO 97/26733 PCT/US97/0O652
Commerce", Denise Caruso, New York Times, August 7, 1995
"Copyrighting in the Information Age", Harley Ungar,
ONLINE MARKETPLACE, September 1995. Jupiter
Communications further describe digital watermarks.
5 Additional information on other methods for hiding
information signals in content signals, is disclosed in
U.S. Patent No. 5,319,735 - Preuss et al . and U.S.
Patent No. 5,3 79,34 5 - Greenberg .
Digital watermarks can be encoded with random or
10 pseudo random keys, which act as secret maps for
locating the watermarks. These keys make it impossible
for a party without the key to find the watermark - in
addition, the encoding method can be enhanced to force a
party to cause damage to a watermarked data stream when
15 trying to erase a random-key watermark.
It is desirable to be able to specify limitations
on the application of such random or pseudo random keys
in encoding a watermark to minimize artifacts in the
content signal while maximizing ■ encoding level. This
preserves the quality of the content, while maximizing
the security of the watermark. Security is maximized
because erasing a watermark without a key results in the
greatest amount of perceptible artifacts in the digital
content, it is also desirable to separate the
25 functionality of the decoder side of the process to
provide fuller recognition and substantiation of the
protection of goods that are essentially digitized bits,
while ensuring the security of the encoder and the
encoded content. It is also desirable that the separate
decoder be incorporated into an agent, virus, search
engine, or other autonomously operating or search
function software. This would make it possible for
parties possessing a decoder to verify the presence of
valid watermarks in a data stream, without accessing the
3 5 contents of the watermark, it would also be possible to
scan or search archives for files containing watermarked
20
30
2
WO 97/26733
PCT/US97/00652
content, and to verify the validity of the presence of
such files in an archive, by means of the information
contained in the watermarks. This scenario has
particular application in screening large archives of
5 files kept by on-line services and internet archives.
It is further a goal of such processes to bring as much
control of copyrights and content, including its
pricing, billing, and distribution, to the parties that
are responsible for creating and administering that
10 content. It is another goal of the invention to provide
a method for encoding multiple watermarks into a digital
work, where each watermark can be accessed by use of a
separate key. This ability can be used to provide
access to watermark information to various parties with
15 different levels of access. It is another goal of the
invention to provide a mechanism which allows for
accommodation of alternative methods encoding and
decoding watermarks from within the same software or
hardware infrastructure. This ability can be used to
2 0 provide upgrades to the watermark system, without
breaking support for decoding watermarks created by
previous versions of the system. It is another goal of
the invention to provide a mechanism for the
certification and authentication, via a trusted third
party, and public forums, of the information placed in a
digital watermark. This provides additional
corroboration of the information contained in a decoded
digital watermark for the purpose of its use in
prosecution of copyright infringement cases.. It also
has use in any situation in which a trusted third party
verification is useful. It is another goal of this
invention to provide an additional method for the
synchronization of watermark decoding software to an
embedded watermark signal, that is more robust than
35 previously disclosed methods.
25
30
3
WO 97/26733
PCT/US97/00652
SUMMARY OF THE INVENTION
The invention described herein is a human-assisted
random key generation and application system for use in
a digital watermark system. The invention allows an
5 engineer or other individual, with specialized knowledge
regarding processing and perception of a particular
content type, such as digital audio or video, to observe
a graphical representation of a subject digital
recording or data stream, in conjunction with its
10 presentation (listening or viewing) and to provide input
to the key generation system that establishes a key
generation "envelope", which determines how the key is
used to apply a digital watermark to the digital data
stream. The envelope limits the parameters of either or
15 both the key generation system and the watermark
application system, providing a rough guide within which
a random or pseudo random key may be automatically
generated and applied. This can provide a good fit to
the content, such that the key may be used to encode a
20 digital watermark into the content in such a manner as
to minimize or limit the perceptible artifacts produced
in the watermarked copy, while maximizing the signal
encoding level. The invention further provides for
variations in creating, retrieving, monitoring and
IS manipulating watermarks to create better and more
flexible approaches to working with copyrights in the
digital domain.
Such a system is described herein and provides the
user with a graphical representation of the content
JO signal over time. In addition, it provides a way for
the user to input constraints on the application of the
digital watermark key, and provides a way to store this
information with a random or pseudo random key sequence
which is also generated to apply to a content signal.
15 Such a system would also be more readily adaptable by
current techniques to master content with personal
4
WO 97/26733
PCT7US97/00652
computers and authoring/editing software. It would also
enable individuals to monitor their copyrights with
decoders to authenticate individual purchases, filter
possible problematic and unpaid copyrightable materials
5 in archives, and provide for a more generally
distributed approach to the monitoring and protection .of
copyrights in the digital domain.
DETAILED DESCRIPTION
10 Digital watermarks are created by encoding an
information signal into a larger content signal. The
information stream is integral with the content stream,
creating a composite stream. The effectiveness and
value of such watermarks are highest when the
15 informational signal is difficult to remove, in the
absence of the key, without causing perceptible
artifacts in the content signal. The watermarked
content signal itself should contain minimal or no
perceptible artifacts of the information signal. To
2 0 make a watermark virtually impossible to find without
permissive use of the key, its encoding is dependent
upon a randomly generated sequence of binary Is and 0s,
which act as the authorization key. Whoever possesses
this key can access the watermark. In effect, the key
25 is a map describing where in the content signal the
information signal is hidden. This represents an
improvement over existing efforts to protect
copyrightable material through hardware -based solutions
always existing outside the actual content.
3 0 "Antipiracy" devices are used in present applications
like VCRs, cable television boxes, and digital audio
tape (DAT) recorders, but are quite often disabled by
those who have some knowledge of the location of the
device or choose not to purchase hardware with these
35 "additional security features." With digital
watermarks, the "protection," or more accurately, the
5
WO 97/26733
PCT/US97/00652
deterrent, is hidden entirely in the signal, rather than
a particular chip in the hardware.
Given a completely random key, which is uniformly
applied over a content signal, resulting artifacts in
5 the watermarked content signal *are unpredictable, and
depend on the interaction of the key and the content
signal itself. One way to ensure minimization of
artifacts is to use a low information signal level.
However, this makes the watermark easier to erase,
10 without causing audible artifacts in the content signal.
This is a weakness. If the information signal level is
boosted, there is the risk of generating audible
artifacts .
The nature of the content signal generally varies
15 significantly over time. During some segments, the
signal may lend itself to masking artifacts that would
otherwise be caused by high level encoding. At other
times, any encoding is likely to cause artifacts. In
addition, it might be worthwhile to encode low signal
2 0 level information in a particular frequency range which
corresponds to important frequency components of the
content signal in a given segment of the content signal .
This would make it difficult to perform bandpass
filtering on the content signal to remove watermarks.
25 Given the benefits of such modifications to the
application of the random key sequence in encoding a
digital watermark, what is needed is a system which
allows human-assisted key generation and application for
digital watermarks. The term "human-assisted key
3 0 generation" is used because in practice, the information
describing how the random or pseudo random sequence key
is to be applied must be stored with the key sequence.
It is, in essence, part of the key itself, since the
random or pseudo random sequence alone is not enough to
3 5 encode, or possibly decode the watermark.
6
WO 97/26733
PCT7US97/00652
Encoding of digital watermarks into a content
signal can be done in the time domain, by modifying
content samples on a sample by sample basis, or in the
frequency domain, by first performing a mathematical
5 transform on a series of content samples in order to
convert them into frequency domain information,
subsequently modifying the frequency domain information
with the watermark, and reverse transforming it back
into time-based samples. The conversion between time
10 and frequency domains can be accomplished by means of
any of a class of mathematical transforms, known in
general as "Fourier Transforms." There are various
algorithmic implementations and optimizations in
computer source code to enable computers to perform such
15 transform calculations. The frequency domain method can
be used to perform "spread spectrum" encoding
implementations. Spread spectrum techniques are
described in the prior art patents disclosed. Some of
the shortcomings evident in these techniques relate to
2 0 the fixed parameters for signal insertion in a sub
audible level of the frequency-based domain, e.g,, U.S,
Patent No. 5,319,735 Preuss et al . A straightforward
randomization attack may be engaged to remove the signal
by simply over- encoding random information continuously
25 in all sub-bands of the spread spectrum signal band,
which is fixed and well defined. Since the Preuss
patent relies on masking effects to render the watermark
signal, which is encoded at -15 dB relative to the
carrier signal, inaudible, such a randomization attack
30 will not result in audible artifacts in the carrier
signal, or degradation of the content. More worrisome,
the signal is not the original but a composite of an
actual frequency in a known domain combined with another
signal to create a "facsimile" or approximation, said to
3 5 be imperceptible to a human observer, of the original
copy. What results is the forced maintenance of one
7
WO 97/26733
PCT/US97/0O652
original to compare against subsequent "suspect" copies
for examination. Human-assisted watermarking would
provide an improvement over the art by providing
flexibility as to where information signals would be
5 inserted into content while giving the content creator
the ability to check all subsequent copies without the
requirement of a single original or master copy for
comparison. Thus the present invention provides for a
system where all necessary information is contained
10 within the watermark itself.
Among other improvements over the art, generation
of keys and encoding with human assistance would allow
for a better match of a given informational signal (be
it an ISRC code, an audio or voice file, serial number,
15 or other "file" format) to the underlying content given
differences in the make-up of the multitudes of forms of
content (classical music, CD-ROM versions of the popular
game DOOM, personal HTML Web pages, virtual reality
simulations, etc.) and the ultimate wishes of the
20 content creator or his agents. This translates into a
better ability to maximize the watermark signal level,
so as to force maximal damage to the content signal when
there is an attempt to erase a watermark without the
key. For instance, an engineer could select only the
25 sections of a digital audio recording where there were
high levels of distortion present in the original
recording, while omitting those sections with relatively
"pure" components from the watermark process. This then
allows the engineer to encode the watermark at a
30 relatively higher signal level in the selected sections
without causing audible artifacts in the signal, since
the changes to the signal caused by the watermark
encoding will be masked by the distortion. A party
wanting to erase the watermark has no idea, however,
35 where or at what level a watermark is encoded, and so
must choose to "erase" at the maximum level across the
8
WO 97/26733
PCT/US97/D0652
entire data stream, to be sure they have obliterated
every instance of a watermark.
In the present invention, the input provided by the
engineer is directly and immediately reflected in a
5 graphical representation of content of that input, in a
manner such that it is overlaid on a representation of
the recorded signal. The key generation "envelope"
described by the engineer can be dictated to vary
dynamically over time, as the engineer chooses* The
10 graphical representation of the content is typically
rendered on a two dimensional computer screen, with a
segment of the signal over time proceeding horizontally
across the screen. The vertical axis is used to
distinguish various frequency bands in the signal, while
15 the cells described by the intersection of vertical and
horizontal unit lines can signify relative amplitude
values by either a brightness or a color value on the
display.
Another possible configuration and operation of the
20 system would use a display mapping time on the
horizontal axis versus signal amplitude on the vertical
axis. This is particularly useful for digital audio
signals. In this case, an engineer could indicate
certain time segments, perhaps those containing a highly
25 distorted signal, to be used for watermark encoding,
while other segments, which contain relatively pure
signals, concentrated in a few bandwidths, may be exempt
from watermarking. The engineer using a time vs.
amplitude assisted key generation configuration would
3 0 generally not input frequency limiting information.
In practice, the system might be used by an
engineer or other user as follows:
The engineer loads a file containing the digitized
content stream to be watermarked onto a computer. The
35 engineer runs the key generation application and opens
the file to be watermarked. The application opens- a
9
WO 97/26733
PCTYUS97/00652
window which contains a graphical representation of the
digitized samples. Typically, for digital audio, the
engineer would see a rectangular area with time on the
horizontal axis, frequency bands on the vertical axis,
and varying color or brightness signifying signal power
at a particular time and frequency band. Each vertical
slice of the rectangle represents the frequency
components, and their respective amplitude, at a
particular instant ("small increment") of time.
Typically, the display also provides means for scrolling
from one end of the stream to the other if it is too
long to fit on the screen, and for zooming in or out
magnification in time or frequency. For the engineer,
this rectangular area acts as a canvas. Using a mouse
and/or keyboard, the engineer can scroll through the
signal slowly marking out time segments or frequency
band minima and maxima which dictate where, at what
frequencies, and at what encoding signal level a
watermark signal is to be encoded into the content,
given a random or pseudo random key sequence . The
engineer may limit these marks to all, none or any of
the types of information discussed above. When the
engineer is finished annotating the content signal, he
or she selects a key generation function. At this
point, all the annotated information is saved in a
record and a random or pseudo random key sequence is
generated associated with other information. At some
later point, this combined key record can be used to
encode and/or decode a watermark into this signal, or
additional instances of it.
A suitable pseudo- random binary sequence for use as
a key may be generated by: collecting some random timing
information based on user keystrokes input to a keyboard
device attached to the computer, performing a secure one
way hash operation on this random timing data, using the
results of the hash to seed a block cipher algorithm
WO 97/26733
PCT/US97/00652
loop, and then cycling the block cipher and collecting a
sequence of Is and Os from the cipher's output, until a
pseudo-random sequence of Is and Os of desired length is
obtained .
5 The key and its application information can then be
saved together in a single database record within a
database established for the purpose of archiving such
information, and sorting and accessing it by particular
criteria. This database should be encrypted with a -
10 passphrase to prevent the theft of its contents from the
storage medium.
Another improvement in the invention is support for
alternate encoding algorithm support. This can be
accomplished for any function which relates to the
15 encoding of the digital watermark by associating with
the pseudo-random string of Is and Os comprising the
pseudo-random key, a list of references to the
appropriate functions for accomplishing the encoding.
For a given function, these references can indicate a
20 particular version of the function to use, or an
entirely new one. The references can take the form of
integer indexes which reference chunks of computer code,
of alphanumeric strings which name such "code
resources," or the memory address of the entry point of
2 5 a piece of code already resident in computer memory.
Such references are not, however, limited to the above
examples. In the implementation of software, based on
this and previous filings, each key contains associated
references to functions identified as CODEC - basic .
3 0 encode/decode algorithm which encodes and decodes bits
of information directly to and from the content signal,
MAP - a function which relates the bits of the key to
the content stream, FILTER - a function which describes
how to pre-filter the content signal, prior to encoding
3 5 or decoding, CIPHER - a function which provides
encryption and decryption services for information
11
WO 97/26733
PCTYUS97/00652
contained in the watermark, and ERRCODE - a function
which further encodes/decodes watermark information so
that errors introduced into a watermark may be corrected
after extraction from the content signal.
5 Additionally, a new method of synchronizing decoder
software to an embedded watermark is described. In a
previous disclosure, a method whereby a marker sequence
of N random bits was generated, and used to signal the
start of an encoded watermark was described. When the
10 decoder recognizes the N bit sequence, it knows it is
synchronized. In that system the chance of a false
positive synchronization was estimated at 1/(N*2) ("one
over (N to the power of 2) ") . While that method is
fairly reliable, it depends on the marker being encoded
15 as part of the steganographic process, into the content
stream. While errors in the encoded bits may be
partially offset by error coding techniques, error
coding the marker will require more computation and
complexity in the system. It also does not completely
20 eliminate the possibility that a randomization attack
can succeed in destroying the marker. A new method is
implemented in which the encoder pre-processes the
digital sample stream, calculating where watermark
information will be encoded. As it is doing this, it
25 notes the starting position of each complete watermark,
and records to a file, a sequence of N-bits representing
sample information corresponding to the start of the
watermark, for instance, the 3rd most significant bit of
the 256 samples immediately preceding the start of a
3 0 watermark. This would be a 256 bit marker. The order in
which these markers are encountered is preserved, as it
is important. The decoder then searches for matches. to
these markers. It processes the markers from first to
last, discarding each as it is found, or possibly not
3 5 found within a certain scanning distance, and proceeding
with the remaining markers . This method does not modify
12
WO 97/26733
PCT/US97/006S2
the original signal with marker information and has the
added benefit that high-significance sequences can be
used, requiring that an attack based on randomizing
markers do very obvious damage to the content stream.
5 With multichannel encoding, both private and public
keys, similar in use to those from public-key
cryptosystems, could be provided for authentication by
concerned third party vendors and consumers, as well as
contribute to better management and protection of
10 copyrights for the digital world that already exist in
the physical world. For more information on public-key
cryptosystems see US Pat No 4,200,770 Dif f ie-Hellman,
4,218,582 Hellman, 4,405,829 RSA, 4,424,414 Hellman
Pohlig. in addition, any number of key "designations"
15 between "public" and "private" could be established, to
provide various access privileges to different groups.
Multi -channel watermarks are effected by encoding
separate watermark certificates with separate keys by
either interleaving windows in the time domain or by
2 0 using separate frequency bands in the frequency domain.
For instance, 3 separate watermarks could be encoded by
using every third sample window processed to encode a
corresponding certificate. Alternatively, complete
watermarks could be interleaved. Similarly, the
25 frequency range of an audio recording might be
partitioned into 3 sub- ranges for such a purpose. Use
of multi -channel watermarks would allow groups with
varying access privileges to access watermark
information in a given content signal. The methods of
30 multichannel encoding would further provide for more
holographic and inexpensive maintenance of copyrights by
parties that have differing levels of access priority as
decided by the ultimate owner or publisher of the
underlying content . Some watermarks could even play
35 significant roles in adhering to given filtering (for
example, content that is not intended for all
13
WO 97/26733
PCT/US97/00652
observers) , distribution, and even pricing schemes for
given pieces of content. Further, on-the-fly
watermarking could enhance identification of pieces of
content that are traded between a number of parties or
5 in a number of levels of distribution. Previously
discussed patents by Preuss et al . and Greenberg and
other similar systems lack this feature.
Further improvements over the prior art include the
general capacity and robustness of the given piece of
10 information that can be inserted into media content with
digital watermarks, described in Steganographic Method
and Device and further modified here, versus "spread
spectrum-only" methods. First, the spread spectrum
technique described in US. Patent No. 5,319,735 Preuss
15 et al. is limited to an encoding rate of 4.3 8-bit
symbols per second within a digital audio signal. this
is because of the nature of reliability requirements for
spread spectrum systems. The methods described in this
invention and those of the previous application,
2 0 "Steganographic Method and Device," do not particularly
adhere to the use of such spread spectrum techniques,
thus removing such limitation. In the steganographic
derived implementation the inventors have developed
based on these filings, watermarks of approximately
25 1,000 bytes (or lOOOx 8 bits) were encoded at a rate of
more than 2 complete watermarks per second into the
carrier signal . The carrier signal was a two channel
(stereo) 16-bit, 44.1 Khz recording. The cited encoding
rate is per channel. This has been successfully tested
3 0 in a number of audio signals. While this capacity is
likely to decrease by 50% or more as a result of future
improvements to the security of the system, it should
still far exceed the 4.3 symbols per second envisioned
by Preuss et al . Second, the ability exists to recover
3 5 the watermarked information with a sample of the overall
piece of digitized content (that is, for instance, being
14
WO 97/26733
PCI7US97/00652
able to recover a watermark from just 10 seconds of a 3
minute song, depending on the robustness or size of the
data in a given watermark) instead of a full original.
Third, the encoding process described in Steganographic
5 Method and Device and further modified in this invention
explicitly seeks to encode the information signal in
such a way with the underlying content signal as to make
destruction of the watermark cause destruction of the
underlying signal. The prior art describes methods that
10 confuse the outright destruction of the underlying
content with "the level of difficulty" of removing or
altering information signals that may destroy underlying
content. This invention anticipates efforts that can be
undertaken with software, such as Digidesign's Sound
15 Designer II or Passport Design's Alchemy, which gives
audio engineers (similar authoring software for video
also exists, for instance, that sold by Avid Technology,
and others as well as the large library of picture
authoring tools) very precise control of digital
20 signals, "embedded" or otherwise, that can be purely
manipulated in the frequency domain. Such software
provides for bandpass filtering and noise elimination
options that may be directed at specific ranges of the
frequency domain, a ripe method for attack in order to
25 hamper recovery of watermark information encoded in
specific frequency ranges. .
Separating the decoder from the encoder can limit
the ability to reverse the encoding process while
providing a reliable method for third parties to be able
30 to make attempts to screen their archives for
watermarked content without being able to tamper with
all of the actual watermarks. This can be further
facilitated by placing separate signals in the content
using the encoder, which signal the presence of a valid
35 watermark, e.g. by providing a "public key accessible"
watermark channel which contains information comprised
15
WO 97/26733
PCT/US97/00652
of a digitally signed digital notary registration of the
watermark in the private channel, along with a checksum
verifying the content stream. The checksum reflects the
unique nature of the actual samples which contain the
5 watermark in question, and therefore woyld p^g^de^a „
means to detect an attempt to graft a watermark lifted
from one recording and placed into another recording in
an attempt to deceive decoding software of the nature of
the recording in question. During encoding, the encoder
10 can leave room within the watermark for the checksum,
and analyze the portion of the content stream which will
contain the watermark in order to generate the checksum
before the wu. earmark is encoded. Once the checksum is
computed, the complete watermark certificate, which now
15 contains the checksum, is signed and/or encrypted, which
prevents modification of any portion of the certificate,
including the checksum, and finally encoded into the
stream. Thus, if it is somehow moved at a later time,
that fact can be detected by decoders. Once the decoder
20 functions are separate from the encoder, watermark
decoding functionality could be embedded in several
types of software including search agents, viruses, and
automated archive scanners. Such software could then be
used to screen files or search out files from archive
25 which contain specific watermark information, types of
watermarks, or lack watermarks. For instance, an online
service could, as policy, refuse to archive any digital
audio file whtcfr does not contain a valid watermark
notarized by?a "trusted digital notary. It could then run
30 automated software to continuously scan its archive for
digital audio files which lack such watermarks, and
erase them.
Watermarks can be generated to contain information
to be used in effecting software or content metering
3 5 services. In order to accomplish this, the watermark
16
WO 97/26733 PCTYUS97/00652
would include various fields selected from the following
information :
title identification;
unit measure;
5 unit price;
percentage transfer threshold at which liability is
incurred to purchaser;
percent of content transferred;
authorized purchaser identification;
10 seller account identification;
payment means identification;
digitally signed information from sender indicating
percent of content transferred; and
digitally signed information from receiver
15 indicating percent of content received.
These "metering" watermarks could be dependent on a near
continuous exchange of information between the
transmitter and receiver of the metered information in
question. The idea is that both sides must agree to ■ what
20 the watermark says, by digitally signing it. The sender
agrees they have sent a certain amount of a certain
title, for instance, and the receiver agrees they have
received it, possibly incurring a liability to pay for
the information once a certain threshold is passed. If
25 the parties disagree, the transaction can be
discontinued before such time. In addition, metering,
watermarks could contain account information or other
payment information which would facilitate the
transaction.
3 0 Watermarks can also be made to contain information
pertaining to geographical or electronic distribution
restrictions, or which contain information on where to
locate other copies of this content, or similar content.
For instance, a watermark might stipulate that a
35 recording is for sale only in the United States, or that
it is to be sold only to persons connecting to an online
17
WO 97/26733
PCT/US97/00652
distribution site from a certain set of internet domain
names, like ".us" for United States, or " .ny" for New
York. Further a watermark might contain one or more URLs
describing online sites where similar content that the
5 buyer of a, .giece of content might be interested in can
be found.
A digital notary could also be used in a more
general way to register, time stamp and authenticate the
information inside a watermark, which is referred to as
10 the certificate. A digital notary processes a document
which contains information and assigns to it a unique
identification number which is a mathematical function
of the contents of the document . The notary also
generally includes a time stamp in the document along
15 with the notary's own digital signature to verify the
date and time it received and "notarized" the document.
After being so notarized, the document cannot be altered
in any way without voiding its mathematically computed
signature. To further enhance trust in' such a system,
2 0 the notary may publish in a public forum, such as a
newspaper, which bears a verifiable date, the
notarization signatures of all documents notarized on a
given date. This process would significantly enhance
the trust placed in a digital watermark extracted for
25 the purpose of use in settling legal disputes over
copyright ownership and infringement.
Other "spread spectrum" techniques described in the
art have predefined time stamps to serve the purpose of
verifying the actual time a particular piece of content
30 is being played by a broadcaster, e.g., U.S. Patent No.
5,379,34 5 Greenberg, not the insertion and control of a
copyright or similar information (such as distribution
path, billing, metering) by the owner or publisher of
the content. The Greenberg patent focuses almost
35 exclusively on concerns of broadcasters, not content
creators who deal with digitized media content when
18
WO 97/26733
PCT/US97/00652
distributing their copyrightable materials to unknown
parties. The methods described are specific to spread
spectrum insertion of signals as "segment timing marks"
to make comparisons against a specific master of the
5 underlying broadcast material-- again with the intention
of specifying if the broadcast was made according to
agreed terms with the advertisers. No provisions are
made for stamping given audio signals or other digital
signals with "purchaser 11 or publisher information to
10 stamp the individual piece of content in a manner
similar to the sales of physical media products (CDs ,
CD-ROMs, etc.) or other products in general (pizza
delivery, direct mail purchases, etc.). In other words,
" interval -defining signals," as described in the
15 Greenberg patent, are important for verification of
broadcasts of a time-based commodity like time and date-
specific, reserved broadcast time, but . have - little use
for individuals trying to specify distribution paths,
pricing, or protect copyrights relating to given content
2 0 which may be used repeatedly by consumers for many
years. It would also lack any provisions for the
"serialization" and identification of individual copies
of media content as it can be distributed or exchanged
on the Internet or in other on-line systems (via
25 telephones, cables, or any other electronic transmission
media) . Finally, the Greenberg patent ties itself
specifically to broadcast infrastructure, with the
described encoding occurring just before transmission of
the content signal via analog or digital broadcast, and
30 decoding occurring upon reception.
While the discussion above has described the
invention and its use within specific embodiments, it
should be clear to those skilled in the art that
numerous modifications may be made to the above without
35 departing from the spirit of the invention, and that the
19
WO 97/26733 PCTYUS97/00652
scope of the above invention is to be limited only by
the claims appended hereto.
20
WO 97/26733
PCT7US97/00652
What is Claimed :
1 l. A method for using a computer to generate a
2 random or pseudo random key for a digital watermark
3 system wherein said random key includes:
4 a random or pseudo random sequence of binary
5 is and Os
6 information describing the application of the
7 random sequence to a stream of digitized samples wherein
8 said information includes:
9 at least one list of time delimiters
10 describing segments of the stream;
11 at least one list of frequency delimiters
12 describing frequency bands to be included in watermark
13 computations; and
14 a signal encoding level;
15 wherein the method comprises the
16 step of receiving human interactive input information
17 used to describe limits on where, at what level, and at
18 what frequencies the random binary information of the
19 random key is to be applied to the stream of digitized
2 0 samples in encoding the digital watermark;
21 wherein said human interactive input
22 information comprises at least one of the following
23 datum:
24 a list of time delimiters;
25 a list of frequency delimiters; and
26 a signal encoding level .
1 2. The method of claim 1 further comprising the
2 step of selecting said stream of digitized samples from
3 a list provided by a computer system.
1 3 . The method of claim 2 further comprising the
2 step of creating and displaying a graphical
3 representation on the display device of the computer
21
WO 97/26733
PCT/US97/00652
4 system, wherein said graphical representation includes a
5 time axis and a signal frequency axis.
1 4. The method of claim 2 further comprising the
2 step of creating and * displaying a graphical
3 representation on the display device of the computer
4 system, wherein said graphical representation includes a
5 time axis and a signal amplitude axis.
1 5. The method of claim 3 or 4 , further comprising
2 the step of updating the graphical display to reflect
3 receipt of new human interactive input information.
1 6. The method of claim 5 further comprising the
2 step of generating a random or pseudo random sequence of
3 Is and Os.
1 7. The method of claim 6 further comprising the
2 step of storing input information in association with
3 the random sequence of Is and Os as a single record in a
4 database of such records.
1 8 . The method of claim 7 wherein the record is
2 encrypted using a pass phrase.
1 9 . The method of claim 1 where the stream of
2 digitized samples contains a digital audio recording.
1 10. The method of claim 1 where the stream of
2 digitized samples to be watermarked contains a digital
3 video recording.
1 11. The method of claim 6 wherein the process of
2 generating the random sequence comprises the steps of:
22
WO 97/26733
PCT7US97/00652
3 (a) collecting a series of random bits
4 derived from keyboard latency intervals in random
5 typing;
6 (b) processing the initial series of random
7 bits through a secure one-way hash function;
8 (c) using the results of one-way hash
9 function to seed a block encryption cipher loop;
10 (d) cycling through the block encryption
11 loop, and extracting the least significant bit of each
12 result after cycle; and
13 (e) concatenating the block encryption output
14 bits into the random key sequence
1 12 . A method of encoding and decoding a digital
2 watermark where the encoder and decoder are separate
3 software applications or hardware devices.
1 13. The method of claim 12 wherein the decoder
2 functionality is embedded in a software search engine,
3 word-wide web-crawler file scanning engine, intelligent
4 agent, or a virus.
1 14. The method of claim 12 wherein the decoder can
2 access only a limited number of watermark channels,
3 corresponding to public watermark keys, or any keys
4 otherwise made available to said decoder.
1 15. The method of claim 12 wherein the decoder is
2 capable of detecting the presence of a valid watermark
3 but not of accessing the information in the watermark.
1 16. The method of claim 12 wherein the encoder
2 places a separate signal, which does not interfere with
3 the watermark, into a content stream, where said
4 separate signal can indicate
23
WO 97/26733
PCT/US97/00652
5 watermark synchronization information, which helps
6 locate watermarks in the content; and
7 the presence of a valid watermark in the content .
1 17. A method of using digital watermarks to convey
2 information which is to be used for a content metering
3 service, wherein said watermarks contain at least one of
4 the following pieces of information:
5 title identification;
6 unit measure;
7 unit price;
8 . percentage transfer threshold at which liability is
9 incurred to purchaser;
10 percent of content transferred;
11 authorized purchaser identification;
12 seller account identification;
13 payment means identification;
14 digitally signed information from sender indicating
15 percent of content transferred; and
16 digitally signed information from receiver
17 indicating percent of content received.
1 18. A method of encoding digital watermarks which
2 contain information pertaining to distribution
3 restrictions and a location of an addressable directory
4 containing related content, where said watermarks
5 contain at least one of the following pieces of
6 information:
7 geographical constraints on distribution (state,
8 country, etc) ;
9 logical constraints on distribution;
10 Universal Resource Locator (URL) ;
11 telephone number;
12 Internet Protocol address;
13 Internet domain name;
14 email address; and
24
WO 97/26733
PCT/US97/00652
15 file name.
1 19. A method of encoding multiple digital
2 watermarks into a single content stream wherein each
3 watermark is encoded with a separate key.
1 20. The method of claim 18 wherein watermark
2 information from each watermark is interleaved in the
3 time domain.
1 21. A method of claim 18 wherein watermark
2 information from each watermark is placed into specific
3 frequency bands, or interleaved in the frequency domain.
1 22. A method of associating with a pseudo-random
2 key, a list of component function references, which
3 dictate what component functions are applied to the
4 encoding and decoding of a digital watermark using the
5 key in question.
1 23 . A method of providing synchronization of a
2 decoder to watermark which consists of the following
3 steps :
4 a) recording a feature of sample stream, or a
5 marker extracted from the sample stream immediately
6 preceding the start of an encoded watermark;
7 b) recording the order in which a list of markers
8 was encountered in the sample stream ;
9 c) storing a list of such markers and the order of
10 their appearance in a file for use by the decoder;
11 d > optionally, associating the stored information
12 of step c) with a watermark key or watermark receipt or
13 content title;
14 e) in the decoder, selecting a marker from the file
15 in step c) such that the selected marker is not previous
25
WO 97/26733
PCT/US97/00652
16 in order to any other marker previously selected in
17 decoding the sample stream in question;
18 f) attempting to find a feature or marker in the
19 portion of the sample stream currently under processing;
20 ^g) at such time as the currently selected marker is
21 deemed unlikely to be found, discarding it and
22 proceeding to step e) ;
23 h) at such time as marker is found, decoding the
24 watermark, then proceeding to step e) unless the sample
25 stream is exhausted.
26
INTERNATIONAL SEARCH REPORT
International application No.
PCT/US97/00652
A. CLASSIFICATION OF SUBJECT MATTER
IPC(6) :H04L 9/00
US CL :380/20
According to International Patent Classification (I PC) or to both national classification and IPC
B. FIELDS SEARCHED .
Minimum documentation searched (classification system followed by class ificaLion symbols)
U.S. : 380/20, 54
Documentation searched other than minimum documentation to the extent that such documents are included in the fields searched
Electronic data base consulted during the international search (name of data base and, where practicable, search terms used)
C. DOCUMENTS CONSIDERED TO BE RELEVANT
Category*
Citation of document, with indication, where appropriate, of the relevant passages
Relevant to claim No.
Y, P
US. A, 5,530.759 (BRAUDAWAY ET AL) 25 June 1996. see
Figs. 1-2.
1-11, 22
| | Further documents are listed in the continuation of Box C. | | See patent family annex.
" Special categories of cited documents:
"A* document defining the general state of the art which is not considered
to be of particular relevance
"E* earlier document published oo or after the international filing date
"L* document which may throw doubt* on priority claim(t> or which is
cited to establish the publication dale of another c tuition or other
special reason (as specified)
*0* document referring to an oral disclosure, use, exhibition or other
means
" P* document published prior to the international filing date but later than
"Y*
later document published after the international filing date or priority
date and not in conflict with the application but cited to understand the
principle or theory underlying the invention
document of particular relevance; the claimed invention cmnnot be
considered novel or cannot be considered u> involve an inventive step
when the document b taken alone
document of particular relevance; the claimed invention cannot be
considered to involve an inventive step when the document a
combined with one or more other such documents, such combination
being obvious to t person skilled in the art
document member of the same patent family
Date of the actual completion of the international search
06 MAY 1997
Date of mailing of the international search report
A9JUNI997/
Name and mailing address of the ISA/US
Commissioner of Patenu and Trademarks
BoxPCT
Washington. D.C. 20231
Facsimile No. (703) 305-3230
AuU^rizcd officer ^^^^-yld<y&~-
/^ALVATORE CANGIALOSI
Telephone No. (703> 305-1837
Form PCTVISA/210 (second sheet)(July 1992)*
INTERNATIONAL SEARCH REPORT
International application No.
PCT/US97/00652
Box I Observations where certain claims were found unsearchable (Continuation of item 1 of first sheet)
This international report has not been established in respect of certain claims under Article 17(2)<a) for the following reasons:
I. | | Claims N os.: ^ ■ , . ... *
because they relate to subject matter not required to be searched by this Authority, namely:
2. £^ Claims Nos.:
because they relate to parts of the international application that do not comply with the prescribed requirements to such
an extent that no meaningful international search can be carried out, specifically:
3. j^] Claims Nos.;
because they are dependent claims and are not drafted in accordance with the second and third sentences of Rule 6.4(a).
Box II Observations where unity of invention is lacking (Continuation of item 2 of first sheet)
This International Searching Authority found multiple inventions in this international application, as follows:
Please See Extra Sheet.
1 \^ As aU required additional search fees were timely paid by the applicant, this international search report covers all searchable
claims.
aU searchable claims could be searched without effort justifying an additional fee, this Authority did not invite payment
of any additional fee.
3 - CI] As only some ofthc required additional search fees were timely paid by the applicant, this international search report covers
only those claims for which fees were paid, specifically claims Nos.:
1 X] No required additional search fees were timely paid by the applicant. Consequently, this international search report is
restricted to the invention first mentioned in the claims; it is covered by claims Nos.:
Ml and 22
Remark on Protest Q The additional search fees were accompanied by the applicant's protest.
| | No protest accompanied the payment of additional search fees.
Form PCT/ISA/210 (continuation of first sheet(l))(July 1992)*
INTERNATIONAL SEARCH REPORT
International application No.
PCT/US97/00652
BOX II. OBSERVATIONS WHERE UNITY OF INVENTION WAS LACKING
This ISA found multiple inventions as follows:
Group I, Claims 1-11, 22. drawn to an method of generating an encrypted digital watermark.
Group II, Claims 12-21 and 23 method of making and using a digital watermark.
The inventions listed as Groups Ml do not relate to a single inventive concept under PCT Rule 13.1 because under PCT
Rule 13.2, they lack the same or corresponding technical features for the following Reasons: The invention of Group I
lack the separate software, hardware devices or content monitoring. The invention of Group II lack the pseudo-Random
key.
Form PCT/ISA/210 (extra sheet)(July 1992)*
THIS PAGE BLANK (M**™)